백준 2263번
오늘 풀어본 문제는 백준의 2263번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.
solved.ac 기준 CLASS
문제 정보
이 문제의 내용과 조건은 다음과 같다.
문제
$n$ 개의 정점을 갖는 이진 트리의 정점에 $1$ 부터 $n$ 까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 $n$ $(1 \le n \le 100,000)$ 이 주어진다. 다음 줄에는 인오더를 나타내는 $n$ 개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다.
출력
첫째 줄에 프리오더를 출력한다.
풀이과정
1번째 시도
문제를 해결하기 위해 사용한 방식은 다음과 같다.
-
트리의 inorder 와 postorder 를 입력받는다.
-
postorder 의 맨 마지막 원소를 루트 노드로 둔 뒤 inorder 에서 인덱스상 앞서는 원소가 마지막으로 등장하는 위치를 찾아낸다.
-
해당 위치를 기준으로 현재 노드의 왼쪽 subtree 와 오른쪽 subtree 를 각각 구성한다. 구성하는 방식은 2, 3 단계를 재귀적으로 반복하는 것이다.
-
트리가 구성되면, preorder 를 출력한다.
이 과정에서 예전에 만들어 둔 BinarySearchTree 클래스를 사용하였고, 위의 방식을 구현한 메소드 등을 추가하는 등의 수정을 거쳤다. 이 과정에서 BinarySearchTree 의 특성인 정렬상태를 유지하기 위해서 pair<int, int> 자료형을 담도록 하였고, 첫 번째 요소에 inorder 에서의 인덱스를 저장하도록 하였다.
코드는 다음과 같이 작성하였다. 제출할 때는 헤더 파일의 코드를 메인 함수가 있는 파일에 붙여넣은 뒤 제출하였다.
binary_search_tree.hpp
#ifndef __BINARY_SEARCH_TREE_HPP__
#define __BINARY_SEARCH_TREE_HPP__
#include <stack>
#include <string>
#include <sstream>
#include <vector>
template <typename T>
class BinarySearchTree {
private:
struct Node {
Node* left;
Node* right;
T value;
Node() : left(nullptr), right(nullptr), value(static_cast<T>(0)) {}
explicit Node(const T& value) : left(nullptr), right(nullptr), value(value) {}
};
Node* head;
Node* construct(const std::vector<T>& postOrder, const std::vector<T>& inOrder, size_t start, size_t end) {
if (start > end) {
return nullptr;
}
size_t leftEnd = end;
Node* curr = new Node(postOrder[end]);
if (start == end) {
return curr;
}
while (start < leftEnd && postOrder[leftEnd] >= curr->value) {
leftEnd--;
}
if (postOrder[leftEnd] < curr->value) {
curr->left = construct(postOrder, inOrder, start, leftEnd);
curr->right = construct(postOrder, inOrder, leftEnd + 1, end - 1);
}
else {
curr->left = nullptr;
curr->right = construct(postOrder, inOrder, leftEnd, end - 1);
}
return curr;
}
void preOrder(Node *currentNode, std::vector<T> &result) {
result.emplace_back(currentNode->value);
if (currentNode->left != nullptr) {
preOrder(currentNode->left, result);
}
if (currentNode->right != nullptr) {
preOrder(currentNode->right, result);
}
}
void inOrder(Node *currentNode, std::vector<T> &result) {
if (currentNode->left != nullptr) {
inOrder(currentNode->left, result);
}
result.emplace_back(currentNode->value);
if (currentNode->right != nullptr) {
inOrder(currentNode->right, result);
}
}
void postOrder(Node *currentNode, std::vector<T> &result) {
if (currentNode->left != nullptr) {
postOrder(currentNode->left, result);
}
if (currentNode->right != nullptr) {
postOrder(currentNode->right, result);
}
result.emplace_back(currentNode->value);
}
public:
BinarySearchTree() : head(nullptr) {}
BinarySearchTree(const std::vector<T>& postOrder, const std::vector<T>& inOrder) : head(nullptr) {
if (postOrder.size() != inOrder.size() || postOrder.empty()) {
return;
}
else if (postOrder.size() == 1) {
head = new Node(postOrder[0]);
return;
}
size_t leftEnd = postOrder.size() - 1;
head = new Node(postOrder.back());
while (leftEnd > 0 && postOrder[leftEnd] >= head->value) {
leftEnd--;
}
if (postOrder[leftEnd] < head->value) {
head->left = construct(postOrder, inOrder, 0, leftEnd);
head->right = construct(postOrder, inOrder, leftEnd + 1, postOrder.size() - 2);
}
else {
head->left = nullptr;
head->right = construct(postOrder, inOrder, leftEnd, postOrder.size() - 2);
}
}
~BinarySearchTree() {
if (head != nullptr) {
std::stack<Node*> s;
s.push(head);
while (!s.empty()) {
Node* currentNode = s.top();
s.pop();
if (currentNode->left != nullptr) {
s.push(currentNode->left);
}
if (currentNode->right != nullptr) {
s.push(currentNode->right);
}
delete currentNode;
}
}
}
void insert(const T& value) {
if (head == nullptr) {
head = new Node(value);
}
else {
Node* currentNode = head;
Node* parentNode = nullptr;
while (currentNode != nullptr) {
parentNode = currentNode;
if (value < currentNode->value) {
currentNode = currentNode->left;
}
else {
currentNode = currentNode->right;
}
}
if (value < parentNode->value) {
parentNode->left = new Node(value);
}
else {
parentNode->right = new Node(value);
}
}
}
void remove(const T& value) {
// TODO: Implement this later
}
bool search(const T& value) {
Node* currentNode = head;
while (currentNode != nullptr) {
if (value < currentNode->value) {
currentNode = currentNode->left;
}
else if (value > currentNode->value) {
currentNode = currentNode->right;
}
else {
return true;
}
}
return false;
}
std::vector<T> preOrder() {
std::vector<T> result;
if (head != nullptr) {
preOrder(head, result);
}
return result;
}
std::vector<T> inOrder() {
std::vector<T> result;
if (head != nullptr) {
inOrder(head, result);
}
return result;
}
std::vector<T> postOrder() {
std::vector<T> result;
if (head != nullptr) {
postOrder(head, result);
}
return result;
}
};
#endif // !__BINARY_SEARCH_TREE_HPP__
main.cpp
#include <bits/stdc++.h>
#include "binary_search_tree.hpp"
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pll = pair<ll, ll>;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin >> n;
vector<pair<int, int>> inOrder(n);
vector<int> indicies(n+1);
vector<pair<int, int>> postOrder(n);
for (int i=0; i<n; i++) {
int elem;
cin >> elem;
inOrder[i] = make_pair(i, elem);
indicies[elem] = i;
}
for (int i=0; i<n; i++) {
int elem;
cin >> elem;
postOrder[i] = make_pair(indicies[elem], elem);
}
BinarySearchTree<pair<int, int>> bst(postOrder, inOrder);
for (auto& elem : bst.preOrder()) {
cout << elem.second << " ";
}
return 0;
}
그러자 모든 테스트 케이스를 통과하고 ‘맞았습니다’가 나오는 것을 확인할 수 있었다.
마무리
문제를 다 풀고 난 뒤에 발견한 것이지만, 새로 만든 메소드 들에 inOrder 인자는 필요가 없다는 것을 알게되었다. 왜냐하면 pair<int, int> 로 값을 저장하는 과정에서 첫 번째 요소에 inorder 기준의 인덱스를 저장해두기 때문이었다. 만약 이 코드를 사용하고자 하는 사람들 중 이 사실이 거슬린다면 수정해서 사용하길 바란다.
풀이 과정의 코드 스니펫에도 올려두긴 했지만, 내가 구현한 BinarySearchTree 자료구조는 내 레포지토리2에서도 확인할 수 있다. 필요한 사람은 참고하길 바란다.
오늘의 PS는 여기까지!
1: https://www.acmicpc.net/problem/2263
2: https://github.com/ChoiCube84/baekjoon-solutions/blob/main/C%2B%2B/custom_data_structures/binary_search_tree.hpp